home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_TOOL / TOOLS / TOOLS_WI / ICON_8 / ICONX_FO / RLARGINT.C < prev    next >
C/C++ Source or Header  |  1990-04-01  |  46KB  |  2,019 lines
  1. #include <math.h>
  2. #include "::h:config.h"
  3. #include "::h:rt.h"
  4. #include "rproto.h"
  5. #include <ctype.h>
  6.  
  7. #ifdef LargeInts
  8.  
  9. extern int over_flow;
  10.  
  11. /*
  12.  *  Conventions:
  13.  *
  14.  *  Bignums entering this module and leaving it are too large to
  15.  *  be represented with T_Integer.  So, externally, a given value
  16.  *  is always T_Integer or always T_Bignum.
  17.  *
  18.  *  Routines outside this module operate on bignums by calling
  19.  *  a routine like
  20.  *
  21.  *      bigadd(da, db, dx)
  22.  *
  23.  *  where da, db, and dx are pointers to tended descriptors.
  24.  *  For the common case where one argument is a T_Integer, these
  25.  *  call routines like
  26.  *
  27.  *      bigaddi(da, IntVal(*db), dx).
  28.  *
  29.  *  The bigxxxi routines can convert an integer to bignum form;
  30.  *  they use itobig.
  31.  *
  32.  *  The routines that actually do the work take (length, address)
  33.  *  pairs specifying unsigned base-B digit strings.  The sign handling
  34.  *  is done in the bigxxx routines.
  35.  */
  36.  
  37. /*
  38.  * Type for doing arithmetic on (2 * NB)-bit nonnegative numbers.
  39.  *  Normally unsigned but may be signed (with NB reduced appropriately)
  40.  *  if unsigned arithmetic is slow.
  41.  */
  42.  
  43. /* The bignum radix, B */
  44.  
  45. #define B            ((word)1 << NB)
  46.  
  47. /* Bignum digits in a word */
  48.  
  49. #define WORDLEN  (WordBits / NB + (WordBits % NB != 0))
  50.  
  51. /* size of a bignum block that will hold an integer */
  52.  
  53. #define INTBIGBLK  sizeof(struct b_bignum) + sizeof(DIGIT) * WORDLEN
  54.  
  55. /* lo(uword d) :            the low digit of a uword
  56.    hi(uword d) :            the rest, d is unsigned
  57.    signed_hi(uword d) :     the rest, d is signed
  58.    dbl(DIGIT a, DIGIT b) : the two-digit uword [a,b] */
  59.  
  60. #define lo(d)        ((d) & (B - 1))
  61. #define hi(d)        ((uword)(d) >> NB)
  62. #define dbl(a,b)     (((uword)(a) << NB) + (b))
  63.  
  64. #if ((-1) >> 1) < 0
  65. #define signed_hi(d) ((word)(d) >> NB)
  66. #else
  67. #define signbit      ((uword)1 << (WordBits - NB - 1))
  68. #define signed_hi(d) ((word)((((uword)(d) >> NB) ^ signbit) - signbit))
  69. #endif
  70.  
  71. /* BigNum(dptr dp) : the struct b_bignum pointed to by dp */
  72.  
  73. #define BigNum(dp)   ((struct b_bignum *)&BlkLoc(*dp)->bignumblk)
  74.  
  75. /* LEN(struct b_bignum *b) : number of significant digits */
  76.  
  77. #define LEN(b)       ((b)->lsd - (b)->msd + 1)
  78.  
  79. /* DIG(struct b_bignum *b, word i): pointer to ith most significant digit */
  80.  
  81. #define DIG(b,i)     (&(b)->digits[(b)->msd+(i)])
  82.  
  83. /* ceil, ln: ceil may be 1 too high in case ln is inaccurate */
  84.  
  85. #undef ceil
  86. #define ceil(x)      ((word)((x) + 1.01))
  87. #define ln(n)        (log((double)n))
  88.  
  89. /* determine the number of words needed for a bignum block with n digits */
  90.  
  91. #define BigNeed(n)   ( ((sizeof(struct b_bignum) + ((n) - 1) * sizeof(DIGIT)) \
  92.                + WordSize - 1) & -WordSize )
  93.  
  94. /* copied from rconv.c */
  95.  
  96. #if !EBCDIC
  97. #define tonum(c)     (isdigit(c) ? (c)-'0' : 10+(((c)|(040))-'a'))
  98. #else 
  99. #define tonum(c)     index("0123456789abcdefghijklmnopqrstuvwsyz", tolower(c))
  100. #endif
  101.  
  102. /* copied from oref.c */
  103.  
  104. #define RandVal      (RanScale*(k_random=(RandA*k_random+RandC)&MaxLong))
  105.  
  106.  
  107. hidden int mkdesc    Params((struct b_bignum *x, dptr dx));
  108. hidden novalue itobig    Params((word i, struct b_bignum *x, dptr dx));
  109.  
  110. hidden novalue decout    Params((FILE *f, DIGIT *n, word l));
  111.  
  112. hidden int bigaddi    Params((dptr da, word i, dptr dx));
  113. hidden int bigsubi    Params((dptr da, word i, dptr dx));
  114. hidden int bigmuli    Params((dptr da, word i, dptr dx));
  115. hidden int bigdivi    Params((dptr da, word i, dptr dx));
  116. hidden int bigmodi    Params((dptr da, word i, dptr dx));
  117. hidden int bigpowi    Params((dptr da, word i, dptr dx));
  118. hidden int bigpowii    Params((word a, word i, dptr dx));
  119. hidden word bigcmpi    Params((dptr da, word i));
  120.  
  121. hidden DIGIT add1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n));
  122. hidden word sub1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n));
  123. hidden novalue mul1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n, word m));
  124. hidden novalue div1    
  125.         Params((DIGIT *a, DIGIT *b, DIGIT *q, DIGIT *r, word m, word n));
  126. hidden novalue compl1    Params((DIGIT *u, DIGIT *w, word n));
  127. hidden word cmp1    Params((DIGIT *u, DIGIT *v, word n));
  128. hidden DIGIT addi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  129. hidden novalue subi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  130. hidden DIGIT muli1    Params((DIGIT *u, word k, int c, DIGIT *w, word n));
  131. hidden DIGIT divi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  132. hidden DIGIT shifti1    Params((DIGIT *u, word k, DIGIT c, DIGIT *w, word n));
  133. hidden word cmpi1    Params((DIGIT *u, word k, word n));
  134.  
  135. hidden novalue bdzero    Params((DIGIT *dest, word l));
  136. hidden novalue bdcopy    Params((DIGIT *src, DIGIT *dest, word l));
  137.  
  138. /*
  139.  * mkdesc -- put value into a descriptor
  140.  */
  141.  
  142. static int mkdesc(x, dx)
  143. struct b_bignum *x;
  144. dptr dx;
  145. {
  146.    word xlen, cmp;
  147.    static DIGIT maxword[WORDLEN] = { 1 << ((WordBits - 1) % NB) };
  148.  
  149.    /* suppress leading zero digits */
  150.  
  151.    while (x->msd != x->lsd && *DIG(x,0) == 0)
  152.       x->msd++;
  153.  
  154.    /* put it into a word if it fits, otherwise return the bignum */
  155.  
  156.    xlen = LEN(x);
  157.  
  158.    if (xlen < WORDLEN ||
  159.        (xlen == WORDLEN && ((cmp = cmp1(DIG(x,0), maxword, WORDLEN)) < 0 ||
  160.         (cmp == (word)0 && x->sign)))) {
  161.       word val = -(word)*DIG(x,0);
  162.       word i;
  163.  
  164.       for (i = x->msd; ++i <= x->lsd; )
  165.          val = (val << NB) - x->digits[i];
  166.       if (!x->sign)
  167.      val = -val;
  168.       dx->dword = D_Integer;
  169.       IntVal(*dx) = val;
  170.       }
  171.    else {
  172.       dx->dword = D_Bignum;
  173.       BlkLoc(*dx) = (union block *)x;
  174.       }
  175.    return Success;
  176. }
  177.  
  178. /*
  179.  *  i -> big
  180.  */
  181.  
  182. static novalue itobig(i, x, dx)
  183. word i;
  184. struct b_bignum *x;
  185. dptr dx;
  186. {
  187.    x->lsd = WORDLEN - 1;
  188.    x->msd = WORDLEN;
  189.    x->sign = 0;
  190.  
  191.    if (i == 0) {
  192.       x->msd--;
  193.       *DIG(x,0) = 0;
  194.       }
  195.    else if (i < 0) {
  196.       word d = lo(i);
  197.  
  198.       if (d != 0) {
  199.          d = B - d;
  200.          i += B;
  201.          }
  202.       i = - signed_hi(i);
  203.       x->msd--;
  204.       *DIG(x,0) = d;
  205.       x->sign = 1;
  206.       }
  207.             
  208.    while (i != 0) {
  209.       x->msd--;
  210.       *DIG(x,0) = lo(i);
  211.       i = hi(i);
  212.       }
  213.  
  214.    dx->dword = D_Bignum;
  215.    BlkLoc(*dx) = (union block *)x;
  216. }
  217.  
  218. /*
  219.  *  string -> bignum 
  220.  */
  221.  
  222. word bigradix(sign, r, s, dx)
  223. int sign;                      /* '-' or not */
  224. int r;                          /* radix 2 .. 36 */
  225. char *s;                        /* input string */
  226. dptr dx;                        /* output T_Integer or T_Bignum */
  227. {
  228.    struct b_bignum *b;
  229.    DIGIT *bd;
  230.    word len;
  231.    int c;
  232.  
  233.    if (r == 0)
  234.       return CvtFail;
  235.    len = ceil(strlen(s) * ln(r) / ln(B));
  236.    if (blkreq(BigNeed(len)) == Error)
  237.       return CvtFail;
  238.    b = alcbignum(len);
  239.    bd = DIG(b,0);
  240.  
  241.    bdzero(bd, len);
  242.  
  243.    if (r < 2 || r > 36)
  244.       return CvtFail;
  245.  
  246.    for (c = *s++; isalnum(c); c = *s++) {
  247.       c = tonum(c);
  248.       if (c >= r)
  249.      return CvtFail;
  250.       muli1(bd, (word)r, c, bd, len);
  251.       }
  252.  
  253.    while (isspace(c))
  254.       c = *s++;
  255.  
  256.    if (c != '\0')
  257.       return CvtFail;
  258.  
  259.    if (sign == '-')
  260.       b->sign = 1;
  261.  
  262.    /* put value into dx and return the type */
  263.  
  264.    (void)mkdesc(b, dx);
  265.    return Type(*dx);
  266. }
  267.  
  268. /*
  269.  *  bignum -> real
  270.  */
  271.  
  272. double bigtoreal(da)
  273. dptr da;
  274. {
  275.    word i;
  276.    double r = 0;
  277.    struct b_bignum *b = &BlkLoc(*da)->bignumblk;
  278.  
  279.    for (i = b->msd; i <= b->lsd; i++)
  280.       r = r * B + b->digits[i];
  281.  
  282.    return (b->sign ? -r : r);
  283. }
  284. /*
  285.  *  real -> bignum
  286.  */
  287.  
  288. int realtobig(da, dx)
  289. dptr da, dx;
  290. {
  291.    double x = BlkLoc(*da)->realblk.realval;
  292.    struct b_bignum *b;
  293.    word i, blen;
  294.    word d;
  295.  
  296.    if (x > 0.9999 * MinLong && x < 0.9999 * MaxLong) {
  297.       MakeInt((word)x, dx);
  298.       return Success;        /* got lucky; a simple integer suffices */
  299.       }
  300.  
  301.    x = x > 0 ? x : -x;
  302.    blen = ln(x) / ln(B) + 0.99;
  303.    for (i = 0; i < blen; i++)
  304.       x /= B;
  305.    if (x >= 1.0) {
  306.       x /= B;
  307.       blen += 1;
  308.       }
  309.  
  310.    if (blkreq(BigNeed(blen)) == Error)
  311.       return Error;
  312.    b = alcbignum(blen);
  313.    for (i = 0; i < blen; i++) {
  314.       d = (x *= B);
  315.       *DIG(b,i) = d;
  316.       x -= d;
  317.       }
  318.      
  319.    b->sign = x < 0;
  320.    return mkdesc(b, dx);
  321. }
  322.  
  323. /*
  324.  *  bignum -> string
  325.  */
  326.  
  327. int bigtos(da, dx)
  328. dptr da, dx;
  329. {
  330.    struct b_bignum *a, *temp;
  331.    word alen = LEN(BigNum(da));
  332.    word slen = ceil(alen * ln(B) / ln(10));
  333.    char *p, *q;
  334.  
  335.    if (strreq(slen) == Error || blkreq(BigNeed(alen)) == Error) 
  336.       return CvtFail;
  337.    a = BigNum(da);
  338.    temp = alcbignum(alen);
  339.    if (a->sign)
  340.       slen++;
  341.    q = alcstr("",slen);
  342.    bdcopy(DIG(a,0), DIG(temp,0), alen);
  343.    p = q += slen;
  344.    while (cmpi1(DIG(temp,0), (word)0, alen))
  345.       *--p = '0' + divi1(DIG(temp,0), (word)10, DIG(temp,0), alen);
  346.    if (a->sign)
  347.       *--p = '-';
  348.    StrLen(*dx) = q - p;
  349.    StrLoc(*dx) = p;
  350.    return Cvt;
  351. }
  352.  
  353. /*
  354.  *  bignum -> file 
  355.  */
  356.  
  357. novalue bigprint(f, da)
  358. FILE *f;
  359. dptr da;
  360. {
  361.    struct b_bignum *a, *temp;
  362.    word alen = LEN(BigNum(da));
  363.    word slen, dlen;
  364.  
  365.    slen = (BlkLoc(*da)->bignumblk.lsd - BlkLoc(*da)->bignumblk.msd + 1);
  366.    dlen = slen * NB * 0.3010299956639812;    /* 1 / log2(10) */
  367.    if (dlen > MaxDigits) {
  368.       fprintf(f, "integer(~%ld)",dlen - 2);    /* center estimate */
  369.       return;
  370.       }
  371.  
  372.    if (blkreq(BigNeed(alen)) == Error) {
  373.       fatalerr(0, NULL);        /* not worth passing this one back */
  374.       }
  375.    temp = alcbignum(alen);
  376.    a = BigNum(da);
  377.    bdcopy(DIG(a,0), DIG(temp,0), alen);
  378.    if (a->sign)
  379.       putc('-', f);
  380.    decout(f, DIG(temp,0), alen);
  381. }
  382.  
  383. static novalue decout(f, n, l)
  384. FILE *f;
  385. DIGIT *n;
  386. word l;
  387. {
  388.    word i = divi1(n, (word)10, n, l);
  389.  
  390.    if (cmpi1(n, (word)0, l))
  391.       decout(f, n, l);
  392.    putc('0' + i, f);
  393. }
  394.  
  395. /*
  396.  *  da -> dx
  397.  */
  398.  
  399. int cpbignum(da, dx)
  400. dptr da, dx;
  401. {
  402.    struct b_bignum *a;
  403.    word alen = LEN(BigNum(da));
  404.    struct b_bignum *x;
  405.  
  406.    if (blkreq(BigNeed(alen)) == Error)
  407.       return Error;
  408.    x = alcbignum(alen);
  409.    a = BigNum(da);
  410.    bdcopy(DIG(a,0), DIG(x,0), alen);
  411.    x->sign = a->sign;
  412.    return mkdesc(x, dx);
  413. }
  414.  
  415. /*
  416.  *  da + db -> dx
  417.  */
  418.  
  419. int bigadd(da, db, dx)
  420. dptr da, db;
  421. dptr dx;
  422. {
  423.    struct b_bignum *x, *a, *b;
  424.    word alen, blen;
  425.    word c;
  426.  
  427.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  428.       alen = LEN(BigNum(da));
  429.       blen = LEN(BigNum(db));
  430.       if (blkreq(BigNeed(alen > blen ? alen + 1 : blen + 1)) == Error)
  431.      return Error;
  432.       a = BigNum(da);
  433.       b = BigNum(db);
  434.       if (a->sign == b->sign) {
  435.          if (alen > blen) {
  436.             x = alcbignum(alen + 1);
  437.             c = add1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen+1), blen);
  438.             *DIG(x,0) = addi1(DIG(a,0), c, DIG(x,1), alen-blen);
  439.             }
  440.          else if (alen == blen) {
  441.             x = alcbignum(alen + 1);
  442.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  443.             }
  444.          else {
  445.             x = alcbignum(blen + 1);
  446.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  447.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  448.             }
  449.          x->sign = a->sign;
  450.          }
  451.       else {
  452.          if (alen > blen) {
  453.             x = alcbignum(alen);
  454.             c = sub1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen), blen);
  455.             subi1(DIG(a,0), -c, DIG(x,0), alen-blen);
  456.             x->sign = a->sign;
  457.             }
  458.          else if (alen == blen) {
  459.             x = alcbignum(alen);
  460.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  461.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  462.                x->sign = a->sign;
  463.                }
  464.             else {
  465.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  466.                x->sign = b->sign;
  467.                }
  468.             }
  469.          else {
  470.             x = alcbignum(blen);
  471.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  472.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  473.             x->sign = b->sign;
  474.             }
  475.          }
  476.       return mkdesc(x, dx);
  477.       }
  478.    else if (Type(*da) == T_Bignum)    /* bignum + integer */
  479.       return bigaddi(da, IntVal(*db), dx);
  480.    else if (Type(*db) == T_Bignum)    /* integer + bignum */
  481.       return bigaddi(db, IntVal(*da), dx);
  482.    else {                             /* integer + integer */
  483.       struct descrip td;
  484.       char tdigits[INTBIGBLK];
  485.  
  486.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  487.       return bigaddi(&td, IntVal(*db), dx);
  488.       }
  489. }
  490.  
  491. /*
  492.  *  da - db -> dx
  493.  */ 
  494.  
  495. int bigsub(da, db, dx)
  496. dptr da, db, dx;
  497. {
  498.    struct descrip td;
  499.    char tdigits[INTBIGBLK];
  500.    struct b_bignum *a, *b, *x;
  501.    word alen, blen;
  502.    word c;
  503.  
  504.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  505.       alen = LEN(BigNum(da));
  506.       blen = LEN(BigNum(db));
  507.       if (blkreq(BigNeed(alen > blen ? alen + 1 : blen + 1)) == Error)
  508.      return Error;
  509.       a = BigNum(da);
  510.       b = BigNum(db);
  511.       if (a->sign != b->sign) {
  512.          if (alen > blen) {
  513.             x = alcbignum(alen + 1);
  514.             c = add1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen+1), blen);
  515.             *DIG(x,0) = addi1(DIG(a,0), c, DIG(x,1), alen-blen);
  516.             }
  517.          else if (alen == blen) {
  518.             x = alcbignum(alen + 1);
  519.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  520.             }
  521.          else {
  522.             x = alcbignum(blen + 1);
  523.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  524.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  525.             }
  526.          x->sign = a->sign;
  527.          }
  528.       else {
  529.          if (alen > blen) {
  530.             x = alcbignum(alen);
  531.             c = sub1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen), blen);
  532.             subi1(DIG(a,0), -c, DIG(x,0), alen-blen);
  533.             x->sign = a->sign;
  534.             }
  535.          else if (alen == blen) {
  536.             x = alcbignum(alen);
  537.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  538.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  539.                x->sign = a->sign;
  540.                }
  541.             else {
  542.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  543.                x->sign = 1 ^ b->sign;
  544.                }
  545.             }
  546.          else {
  547.             x = alcbignum(blen);
  548.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  549.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  550.             x->sign = 1 ^ b->sign;
  551.             }
  552.          }
  553.       return mkdesc(x, dx);
  554.       }
  555.    else if (Type(*da) == T_Bignum)     /* bignum - integer */
  556.       return bigsubi(da, IntVal(*db), dx);
  557.    else if (Type(*db) == T_Bignum) {   /* integer - bignum */
  558.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  559.       alen = LEN(BigNum(&td));
  560.       blen = LEN(BigNum(db));
  561.       if (blkreq(BigNeed(alen > blen ? alen + 1 : blen + 1)) == Error)
  562.      return Error;
  563.       a = BigNum(&td);
  564.       b = BigNum(db);
  565.       if (a->sign != b->sign) {
  566.          if (alen == blen) {
  567.             x = alcbignum(alen + 1);
  568.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  569.             }
  570.          else {
  571.             x = alcbignum(blen + 1);
  572.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  573.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  574.             }
  575.          x->sign = a->sign;
  576.          }
  577.       else {
  578.          if (alen == blen) {
  579.             x = alcbignum(alen);
  580.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  581.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  582.                x->sign = a->sign;
  583.                }
  584.             else {
  585.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  586.                x->sign = 1 ^ b->sign;
  587.                }
  588.             }
  589.          else {
  590.             x = alcbignum(blen);
  591.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  592.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  593.             x->sign = 1 ^ b->sign;
  594.             }
  595.          }
  596.       return mkdesc(x, dx);
  597.       }
  598.    else {                              /* integer - integer */
  599.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  600.       return bigsubi(&td, IntVal(*db), dx);
  601.       }
  602.       
  603. }
  604.  
  605. /*
  606.  *  da * db -> dx
  607.  */
  608.  
  609. int bigmul(da, db, dx)
  610. dptr da, db, dx;
  611. {
  612.    struct b_bignum *a, *b, *x;
  613.    word alen, blen;
  614.  
  615.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  616.       alen = LEN(BigNum(da));
  617.       blen = LEN(BigNum(db));
  618.       if (blkreq(BigNeed(alen + blen)) == Error)
  619.      return Error;
  620.       a = BigNum(da);
  621.       b = BigNum(db);
  622.       x = alcbignum(alen + blen);
  623.       mul1(DIG(a,0), DIG(b,0), DIG(x,0), alen, blen);
  624.       x->sign = a->sign ^ b->sign;
  625.       return mkdesc(x, dx);
  626.       }
  627.    else if (Type(*da) == T_Bignum)    /* bignum * integer */
  628.       return bigmuli(da, IntVal(*db), dx);
  629.    else if (Type(*db) == T_Bignum)    /* integer * bignum */
  630.       return bigmuli(db, IntVal(*da), dx);
  631.    else {                             /* integer * integer */
  632.       struct descrip td;
  633.       char tdigits[INTBIGBLK];
  634.  
  635.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  636.       return bigmuli(&td, IntVal(*db), dx);
  637.       }
  638. }
  639.  
  640. /*
  641.  *  da / db -> dx
  642.  */
  643.  
  644. int bigdiv(da, db, dx)
  645. dptr da, db, dx;
  646. {
  647.    struct b_bignum *a, *b, *x;
  648.    word alen, blen;
  649.  
  650.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  651.       alen = LEN(BigNum(da));
  652.       blen = LEN(BigNum(db));
  653.       if (alen < blen) {
  654.          MakeInt(0, dx);
  655.          return Success;
  656.          }
  657.       if (blkreq(BigNeed(alen-blen+1)+BigNeed(alen+1)+BigNeed(blen)) == Error)
  658.      return Error;
  659.       a = BigNum(da);
  660.       b = BigNum(db);
  661.       x = alcbignum(alen - blen + 1);
  662.       if (blen == 1)
  663.          divi1(DIG(a,0), (word)*DIG(b,0), DIG(x,0), alen);
  664.       else
  665.          div1(DIG(a,0), DIG(b,0), DIG(x,0), NULL, alen-blen, blen);
  666.       x->sign = a->sign ^ b->sign;
  667.       return mkdesc(x, dx);
  668.       }
  669.    else if (Type(*da) == T_Bignum)     /* bignum / integer */
  670.       return bigdivi(da, IntVal(*db), dx);
  671.    else if (Type(*db) == T_Bignum) {   /* integer / bignum */
  672.       MakeInt(0, dx);
  673.       return Success;
  674.       }
  675.    /* not called for integer / integer */
  676. }
  677.  
  678. /*
  679.  *  da % db -> dx
  680.  */
  681.  
  682. int bigmod(da, db, dx)
  683. dptr da, db, dx;
  684. {
  685.    struct b_bignum *a, *b, *x, *temp;
  686.    word alen, blen;
  687.  
  688.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  689.       alen = LEN(BigNum(da));
  690.       blen = LEN(BigNum(db));
  691.       if (alen < blen) {
  692.          cpbignum(da, dx);
  693.          return Success;
  694.          }
  695.       if (blkreq(BigNeed(blen)+BigNeed(alen+1)+BigNeed(blen)) == Error)
  696.      return Error;
  697.       a = BigNum(da);
  698.       b = BigNum(db);
  699.       x = alcbignum(blen);
  700.       if (blen == 1) {
  701.      temp = alcbignum(alen);
  702.          *DIG(x,0) = divi1(DIG(a,0), (word)*DIG(b,0), DIG(temp,0), alen);
  703.          }
  704.       else
  705.          div1(DIG(a,0), DIG(b,0), NULL, DIG(x,0), alen-blen, blen);
  706.       x->sign = a->sign;
  707.       return mkdesc(x, dx);
  708.       }
  709.    else if (Type(*da) == T_Bignum)     /* bignum % integer */
  710.       return bigmodi(da, IntVal(*db), dx);
  711.    else if (Type(*db) == T_Bignum) {   /* integer % bignum */
  712.       struct descrip td;
  713.       char tdigits[INTBIGBLK];
  714.  
  715.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  716.       cpbignum(&td, dx);
  717.       return Success;
  718.       }
  719.    /* not called for integer % integer */
  720. }
  721.  
  722. /*
  723.  *  -i -> dx
  724.  */
  725.  
  726. int bigneg(da, dx)
  727. dptr da, dx;
  728. {
  729.    struct descrip td;
  730.    char tdigits[INTBIGBLK];
  731.  
  732.    itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  733.    BigNum(&td)->sign ^= 1;
  734.    return cpbignum(&td, dx);
  735. }
  736.  
  737. /*
  738.  *  da ^ db -> dx
  739.  */
  740.  
  741. int bigpow(da, db, dx)
  742. dptr da, db, dx;
  743. {
  744.    word n;
  745.  
  746.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  747.       if (BigNum(db)->sign) {
  748.          MakeInt(0, dx);
  749.          }
  750.       else {
  751.          n = LEN(BigNum(db)) * NB;
  752.          /* scan bits left to right.  skip leading 1. */
  753.          while (--n >= 0)
  754.             if ((*DIG(BigNum(db), n / NB) & (1 << (n % NB))))
  755.                break;
  756.          /* then, for each zero, square the partial result;
  757.           *  for each one, square it and multiply it by a */
  758.          *dx = *da;
  759.          while (--n >= 0) {
  760.             if (bigmul(dx, dx, dx) == Error)
  761.            return Error;
  762.             if ((*DIG(BigNum(db), n / NB) & (1 << (n % NB))))
  763.                if (bigmul(dx, da, dx) == Error)
  764.           return Error;
  765.         }
  766.          }
  767.       return Success;
  768.       }
  769.    else if (Type(*da) == T_Bignum)    /* bignum ^ integer */
  770.       return bigpowi(da, IntVal(*db), dx);
  771.    else if (Type(*db) == T_Bignum)    /* integer ^ bignum */
  772.       return bigpowii(IntVal(*da), (word)bigtoreal(db), dx);
  773.    else                               /* integer ^ integer */
  774.       return bigpowii(IntVal(*da), IntVal(*db), dx);
  775. }
  776.  
  777. /*
  778.  *  iand(da, db) -> dx
  779.  */
  780.  
  781. int bigand(da, db, dx)
  782. dptr da, db, dx;
  783. {
  784.    struct b_bignum *a, *b, *x;
  785.    word alen, blen, xlen;
  786.    word i;
  787.    struct b_bignum *tad, *tbd;
  788.    DIGIT *ad, *bd;
  789.    struct descrip td;
  790.    char tdigits[INTBIGBLK];
  791.  
  792.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  793.       alen = LEN(BigNum(da));
  794.       blen = LEN(BigNum(db));
  795.       xlen = alen > blen ? alen : blen;
  796.       if (blkreq(3 * BigNeed(xlen)) == Error)
  797.          return Error;
  798.       a = BigNum(da);
  799.       b = BigNum(db);
  800.       x = alcbignum(xlen);
  801.  
  802.       if (alen == xlen && !a->sign)
  803.          ad = DIG(a,0);
  804.       else {
  805.          tad = alcbignum(xlen);
  806.          ad = DIG(tad,0);
  807.          bdzero(ad, xlen - alen);
  808.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  809.          if (a->sign)
  810.         compl1(ad, ad, xlen);
  811.          }
  812.  
  813.       if (blen == xlen && !b->sign)
  814.          bd = DIG(b,0);
  815.       else {
  816.          tbd = alcbignum(xlen);
  817.          bd = DIG(tbd,0);
  818.          bdzero(bd, xlen - blen);
  819.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  820.          if (b->sign)
  821.         compl1(bd, bd, xlen);
  822.          }
  823.         
  824.       for (i = 0; i < xlen; i++)
  825.          *DIG(x,i) = ad[i] & bd[i];
  826.  
  827.       if (a->sign & b->sign) {
  828.          x->sign = 1;
  829.          compl1(DIG(x,0), DIG(x,0), xlen);
  830.          }
  831.       }
  832.    else if (Type(*da) == T_Bignum) {   /* iand(bignum,integer) */
  833.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  834.       alen = LEN(BigNum(da));
  835.       blen = LEN(BigNum(&td));
  836.       xlen = alen > blen ? alen : blen;
  837.       if (blkreq(3 * BigNeed(alen)) == Error)
  838.          return Error;
  839.       a = BigNum(da);
  840.       b = BigNum(&td);
  841.       x = alcbignum(alen);
  842.  
  843.       if (alen == xlen && !a->sign)
  844.          ad = DIG(a,0);
  845.       else {
  846.          tad = alcbignum(xlen);
  847.          ad = DIG(tad,0);
  848.          bdzero(ad, xlen - alen);
  849.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  850.          if (a->sign)
  851.         compl1(ad, ad, xlen);
  852.          }
  853.  
  854.       if (blen == xlen && !b->sign)
  855.          bd = DIG(b,0);
  856.       else {
  857.          tbd = alcbignum(xlen);
  858.          bd = DIG(tbd,0);
  859.          bdzero(bd, xlen - blen);
  860.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  861.          if (b->sign)
  862.         compl1(bd, bd, xlen);
  863.          }
  864.         
  865.       for (i = 0; i < xlen; i++)
  866.          *DIG(x,i) = ad[i] & bd[i];
  867.  
  868.       if (a->sign & b->sign) {
  869.          x->sign = 1;
  870.          compl1(DIG(x,0), DIG(x,0), xlen);
  871.          }
  872.       }
  873.    else if (Type(*db) == T_Bignum) {   /* iand(integer,bignum) */
  874.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  875.       alen = LEN(BigNum(&td));
  876.       blen = LEN(BigNum(db));
  877.       xlen = alen > blen ? alen : blen;
  878.       if (blkreq(3 * BigNeed(blen)) == Error)
  879.          return Error;
  880.       a = BigNum(&td);
  881.       b = BigNum(db);
  882.       x = alcbignum(blen);
  883.  
  884.       if (alen == xlen && !a->sign)
  885.          ad = DIG(a,0);
  886.       else {
  887.          tad = alcbignum(xlen);
  888.          ad = DIG(tad,0);
  889.          bdzero(ad, xlen - alen);
  890.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  891.          if (a->sign)
  892.         compl1(ad, ad, xlen);
  893.          }
  894.  
  895.       if (blen == xlen && !b->sign)
  896.          bd = DIG(b,0);
  897.       else {
  898.          tbd = alcbignum(xlen);
  899.          bd = DIG(tbd,0);
  900.          bdzero(bd, xlen - blen);
  901.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  902.          if (b->sign)
  903.         compl1(bd, bd, xlen);
  904.          }
  905.         
  906.       for (i = 0; i < xlen; i++)
  907.          *DIG(x,i) = ad[i] & bd[i];
  908.  
  909.       if (a->sign & b->sign) {
  910.          x->sign = 1;
  911.          compl1(DIG(x,0), DIG(x,0), xlen);
  912.          }
  913.       }
  914.    /* not called for iand(integer,integer) */
  915.  
  916.    return mkdesc(x, dx);
  917. }
  918.  
  919. /*
  920.  *  ior(da, db) -> dx
  921.  */
  922.  
  923. int bigor(da, db, dx)
  924. dptr da, db, dx;
  925. {
  926.    struct b_bignum *a, *b, *x;
  927.    word alen, blen, xlen;
  928.    word i;
  929.    struct b_bignum *tad, *tbd;
  930.    DIGIT *ad, *bd;
  931.    struct descrip td;
  932.    char tdigits[INTBIGBLK];
  933.  
  934.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  935.       alen = LEN(BigNum(da));
  936.       blen = LEN(BigNum(db));
  937.       xlen = alen > blen ? alen : blen;
  938.       if (blkreq(3 * BigNeed(xlen)) == Error)
  939.          return Error;
  940.       a = BigNum(da);
  941.       b = BigNum(db);
  942.       x = alcbignum(xlen);
  943.  
  944.       if (alen == xlen && !a->sign)
  945.          ad = DIG(a,0);
  946.       else {
  947.          tad = alcbignum(xlen);
  948.          ad = DIG(tad,0);
  949.          bdzero(ad, xlen - alen);
  950.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  951.          if (a->sign)
  952.         compl1(ad, ad, xlen);
  953.          }
  954.  
  955.       if (blen == xlen && !b->sign)
  956.          bd = DIG(b,0);
  957.       else {
  958.          tbd = alcbignum(xlen);
  959.          bd = DIG(tbd,0);
  960.          bdzero(bd, xlen - blen);
  961.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  962.          if (b->sign)
  963.         compl1(bd, bd, xlen);
  964.          }
  965.         
  966.       for (i = 0; i < xlen; i++)
  967.          *DIG(x,i) = ad[i] | bd[i];
  968.  
  969.       if (a->sign | b->sign) {
  970.          x->sign = 1;
  971.          compl1(DIG(x,0), DIG(x,0), xlen);
  972.          }
  973.       }
  974.    else if (Type(*da) == T_Bignum) {   /* ior(bignum,integer) */
  975.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  976.       alen = LEN(BigNum(da));
  977.       blen = LEN(BigNum(&td));
  978.       xlen = alen > blen ? alen : blen;
  979.       if (blkreq(3 * BigNeed(alen)) == Error)
  980.          return Error;
  981.       a = BigNum(da);
  982.       b = BigNum(&td);
  983.       x = alcbignum(alen);
  984.  
  985.       if (alen == xlen && !a->sign)
  986.          ad = DIG(a,0);
  987.       else {
  988.          tad = alcbignum(xlen);
  989.          ad = DIG(tad,0);
  990.          bdzero(ad, xlen - alen);
  991.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  992.          if (a->sign)
  993.         compl1(ad, ad, xlen);
  994.          }
  995.  
  996.       if (blen == xlen && !b->sign)
  997.          bd = DIG(b,0);
  998.       else {
  999.          tbd = alcbignum(xlen);
  1000.          bd = DIG(tbd,0);
  1001.          bdzero(bd, xlen - blen);
  1002.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1003.          if (b->sign)
  1004.         compl1(bd, bd, xlen);
  1005.          }
  1006.         
  1007.       for (i = 0; i < xlen; i++)
  1008.          *DIG(x,i) = ad[i] | bd[i];
  1009.  
  1010.       if (a->sign | b->sign) {
  1011.          x->sign = 1;
  1012.          compl1(DIG(x,0), DIG(x,0), xlen);
  1013.          }
  1014.       }
  1015.    else if (Type(*db) == T_Bignum) {   /* ior(integer,bignym) */
  1016.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1017.       alen = LEN(BigNum(&td));
  1018.       blen = LEN(BigNum(db));
  1019.       xlen = alen > blen ? alen : blen;
  1020.       if (blkreq(3 * BigNeed(blen)) == Error)
  1021.          return Error;
  1022.       a = BigNum(&td);
  1023.       b = BigNum(db);
  1024.       x = alcbignum(blen);
  1025.  
  1026.       if (alen == xlen && !a->sign)
  1027.          ad = DIG(a,0);
  1028.       else {
  1029.          tad = alcbignum(xlen);
  1030.          ad = DIG(tad,0);
  1031.          bdzero(ad, xlen - alen);
  1032.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1033.          if (a->sign)
  1034.         compl1(ad, ad, xlen);
  1035.          }
  1036.  
  1037.       if (blen == xlen && !b->sign)
  1038.          bd = DIG(b,0);
  1039.       else {
  1040.          tbd = alcbignum(xlen);
  1041.          bd = DIG(tbd,0);
  1042.          bdzero(bd, xlen - blen);
  1043.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1044.          if (b->sign)
  1045.         compl1(bd, bd, xlen);
  1046.          }
  1047.         
  1048.       for (i = 0; i < xlen; i++)
  1049.          *DIG(x,i) = ad[i] | bd[i];
  1050.  
  1051.       if (a->sign | b->sign) {
  1052.          x->sign = 1;
  1053.          compl1(DIG(x,0), DIG(x,0), xlen);
  1054.          }
  1055.       }
  1056.    /* not called for ior(integer,integer) */
  1057.  
  1058.    return mkdesc(x, dx);
  1059. }
  1060.  
  1061. /*
  1062.  *  xor(da, db) -> dx
  1063.  */
  1064.  
  1065. int bigxor(da, db, dx)
  1066. dptr da, db, dx;
  1067. {
  1068.    struct b_bignum *a, *b, *x;
  1069.    word alen, blen, xlen;
  1070.    word i;
  1071.    struct b_bignum *tad, *tbd;
  1072.    DIGIT *ad, *bd;
  1073.    struct descrip td;
  1074.    char tdigits[INTBIGBLK];
  1075.  
  1076.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  1077.       alen = LEN(BigNum(da));
  1078.       blen = LEN(BigNum(db));
  1079.       xlen = alen > blen ? alen : blen;
  1080.       if (blkreq(3 * BigNeed(xlen)) == Error)
  1081.          return Error;
  1082.       a = BigNum(da);
  1083.       b = BigNum(db);
  1084.       x = alcbignum(xlen);
  1085.  
  1086.       if (alen == xlen && !a->sign)
  1087.          ad = DIG(a,0);
  1088.       else {
  1089.          tad = alcbignum(xlen);
  1090.          ad = DIG(tad,0);
  1091.          bdzero(ad, xlen - alen);
  1092.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1093.          if (a->sign)
  1094.         compl1(ad, ad, xlen);
  1095.          }
  1096.  
  1097.       if (blen == xlen && !b->sign)
  1098.          bd = DIG(b,0);
  1099.       else {
  1100.          tbd = alcbignum(xlen);
  1101.          bd = DIG(tbd,0);
  1102.          bdzero(bd, xlen - blen);
  1103.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1104.          if (b->sign)
  1105.         compl1(bd, bd, xlen);
  1106.          }
  1107.  
  1108.       for (i = 0; i < xlen; i++)
  1109.          *DIG(x,i) = ad[i] ^ bd[i];
  1110.  
  1111.       if (a->sign ^ b->sign) {
  1112.          x->sign = 1;
  1113.          compl1(DIG(x,0), DIG(x,0), xlen);
  1114.          }
  1115.       }
  1116.    else if (Type(*da) == T_Bignum) {   /* ixor(bignum,integer) */
  1117.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  1118.       alen = LEN(BigNum(da));
  1119.       blen = LEN(BigNum(&td));
  1120.       xlen = alen > blen ? alen : blen;
  1121.       if (blkreq(3 * BigNeed(alen)) == Error)
  1122.          return Error;
  1123.       a = BigNum(da);
  1124.       b = BigNum(&td);
  1125.       x = alcbignum(alen);
  1126.  
  1127.       if (alen == xlen && !a->sign)
  1128.          ad = DIG(a,0);
  1129.       else {
  1130.          tad = alcbignum(xlen);
  1131.          ad = DIG(tad,0);
  1132.          bdzero(ad, xlen - alen);
  1133.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1134.          if (a->sign)
  1135.         compl1(ad, ad, xlen);
  1136.          }
  1137.  
  1138.       if (blen == xlen && !b->sign)
  1139.          bd = DIG(b,0);
  1140.       else {
  1141.          tbd = alcbignum(xlen);
  1142.          bd = DIG(tbd,0);
  1143.          bdzero(bd, xlen - blen);
  1144.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1145.          if (b->sign)
  1146.         compl1(bd, bd, xlen);
  1147.          }
  1148.  
  1149.       for (i = 0; i < xlen; i++)
  1150.          *DIG(x,i) = ad[i] ^ bd[i];
  1151.  
  1152.       if (a->sign ^ b->sign) {
  1153.          x->sign = 1;
  1154.          compl1(DIG(x,0), DIG(x,0), xlen);
  1155.          }
  1156.       }
  1157.    else if (Type(*db) == T_Bignum) {   /* ixor(integer,bignum) */
  1158.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1159.       alen = LEN(BigNum(&td));
  1160.       blen = LEN(BigNum(db));
  1161.       xlen = alen > blen ? alen : blen;
  1162.       if (blkreq(3 * BigNeed(blen)) == Error)
  1163.          return Error;
  1164.       a = BigNum(&td);
  1165.       b = BigNum(db);
  1166.       x = alcbignum(blen);
  1167.  
  1168.       if (alen == xlen && !a->sign)
  1169.          ad = DIG(a,0);
  1170.       else {
  1171.          tad = alcbignum(xlen);
  1172.          ad = DIG(tad,0);
  1173.          bdzero(ad, xlen - alen);
  1174.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1175.          if (a->sign)
  1176.         compl1(ad, ad, xlen);
  1177.          }
  1178.  
  1179.       if (blen == xlen && !b->sign)
  1180.          bd = DIG(b,0);
  1181.       else {
  1182.          tbd = alcbignum(xlen);
  1183.          bd = DIG(tbd,0);
  1184.          bdzero(bd, xlen - blen);
  1185.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1186.          if (b->sign)
  1187.         compl1(bd, bd, xlen);
  1188.          }
  1189.  
  1190.       for (i = 0; i < xlen; i++)
  1191.          *DIG(x,i) = ad[i] ^ bd[i];
  1192.  
  1193.       if (a->sign ^ b->sign) {
  1194.          x->sign = 1;
  1195.          compl1(DIG(x,0), DIG(x,0), xlen);
  1196.          }
  1197.       }
  1198.    /* not called for ixor(integer,integer) */
  1199.  
  1200.    return mkdesc(x, dx);
  1201. }
  1202.  
  1203. /*
  1204.  *  bigshift(da, db) -> dx
  1205.  */
  1206.  
  1207. int bigshift(da, db, dx)
  1208. dptr da, db, dx;
  1209. {
  1210.    struct b_bignum *a, *x;
  1211.    word alen;
  1212.    word r = IntVal(*db) % NB;
  1213.    word q = (r >= 0 ? IntVal(*db) : (IntVal(*db) - (r += NB))) / NB;
  1214.    word xlen;
  1215.    DIGIT *ad;
  1216.  
  1217.    if (Type(*da) == T_Bignum) {
  1218.       alen = LEN(BigNum(da));
  1219.       xlen = alen + q + 1;
  1220.       if (xlen <= 0) {
  1221.          MakeInt(0, dx);
  1222.          return Success;
  1223.          }
  1224.       else {
  1225.          if (blkreq(BigNeed(xlen) + BigNeed(alen)) == Error)
  1226.         return Error;
  1227.          a = BigNum(da);
  1228.          x = alcbignum(xlen);
  1229.          ad = DIG(a,0);
  1230.  
  1231.          if (q >= 0) {
  1232.             *DIG(x,0) = shifti1(ad, r, (DIGIT)0, DIG(x,1), alen);
  1233.             bdzero(DIG(x,alen+1), q);
  1234.             x->sign = a->sign;
  1235.             }
  1236.          else  {
  1237.             *DIG(x,0) = shifti1(ad, r, ad[alen+q] >> (NB-r), DIG(x,1), alen+q);
  1238.             }
  1239.  
  1240.          return mkdesc(x, dx);
  1241.      }
  1242.       }
  1243.    else {                              /* da is integer */
  1244.       struct descrip td;
  1245.       char tdigits[INTBIGBLK];
  1246.  
  1247.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1248.       alen = LEN(BigNum(&td));
  1249.       xlen = alen + q + 1;
  1250.       if (xlen <= 0) {
  1251.          MakeInt(0, dx);
  1252.          return Success;
  1253.          }
  1254.       else {
  1255.          if (blkreq(BigNeed(xlen) + BigNeed(alen)) == Error)
  1256.         return Error;
  1257.          a = BigNum(&td);
  1258.          x = alcbignum(xlen);
  1259.          ad = DIG(a,0);
  1260.  
  1261.          if (q >= 0) {
  1262.             *DIG(x,0) = shifti1(ad, r, (DIGIT)0, DIG(x,1), alen);
  1263.             bdzero(DIG(x,alen+1), q);
  1264.             x->sign = a->sign;
  1265.             }
  1266.          else 
  1267.             *DIG(x,0) = shifti1(ad, r, ad[alen+q] >> (NB-r), DIG(x,1), alen+q);
  1268.  
  1269.          return mkdesc(x, dx);
  1270.          }
  1271.       }
  1272. }
  1273.  
  1274. /*
  1275.  *  negative if da < db
  1276.  *  zero if da == db
  1277.  *  positive if da > db
  1278.  */
  1279.  
  1280. word bigcmp(da, db)
  1281. dptr da, db;
  1282. {
  1283.    struct b_bignum *a = BigNum(da);
  1284.    struct b_bignum *b = BigNum(db);
  1285.    word alen, blen; 
  1286.  
  1287.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  1288.       if (a->sign != b->sign)
  1289.          return (b->sign - a->sign);
  1290.       alen = LEN(a);
  1291.       blen = LEN(b);
  1292.       if (alen != blen)
  1293.          return (a->sign ? blen - alen : alen - blen);
  1294.  
  1295.       if (a->sign)
  1296.          return cmp1(DIG(b,0), DIG(a,0), alen);
  1297.       else
  1298.          return cmp1(DIG(a,0), DIG(b,0), alen);
  1299.       }
  1300.    else if (Type(*da) == T_Bignum)    /* cmp(bignum, integer) */
  1301.       return bigcmpi(da, IntVal(*db));
  1302.    else                               /* cmp(integer, bignum) */
  1303.       return -bigcmpi(db, IntVal(*da));
  1304. }
  1305.  
  1306. /*
  1307.  *  ?da -> dx
  1308.  */  
  1309.  
  1310. int bigrand(da, dx)
  1311. dptr da, dx;
  1312. {
  1313.    struct b_bignum *a;
  1314.    word alen = LEN(BigNum(da));
  1315.    struct b_bignum *x;
  1316.    struct b_bignum *td;
  1317.    DIGIT *d;
  1318.    word i;
  1319.    double rval;
  1320.  
  1321.    if (blkreq(4 * BigNeed(alen + 1) + 4) == Error)
  1322.       return Error;
  1323.    x = alcbignum(alen);
  1324.    td = alcbignum(alen + 1);
  1325.    d = DIG(td,0);
  1326.    a = BigNum(da);
  1327.  
  1328.    for (i = alen; i >= 0; i--) {
  1329.       rval = RandVal;
  1330.       d[i] = rval * B;
  1331.       }
  1332.     
  1333.    div1(d, DIG(a,0), NULL, DIG(x,0), (word)1, alen);
  1334.    addi1(DIG(x,0), (word)1, DIG(x,0), alen);
  1335.    return mkdesc(x, dx);
  1336. }
  1337.  
  1338. /*
  1339.  *  da + i -> dx
  1340.  */
  1341.  
  1342. static int bigaddi(da, i, dx)
  1343. dptr da, dx;
  1344. word i;
  1345. {
  1346.    struct b_bignum *a, *x; 
  1347.    word alen; 
  1348.  
  1349.    if (i < 0)
  1350.       return bigsubi(da, -i, dx);
  1351.    else if (i != (DIGIT)i) {
  1352.       struct descrip td;
  1353.       char tdigits[INTBIGBLK];
  1354.  
  1355.       itobig(i, (struct b_bignum *)tdigits, &td);
  1356.       return bigadd(da, &td, dx);
  1357.       }
  1358.    else {
  1359.       alen = LEN(BigNum(da));
  1360.       if (blkreq(BigNeed(alen + 1)) == Error)
  1361.          return Error;
  1362.       a = BigNum(da);
  1363.       if (a->sign) {
  1364.      x = alcbignum(alen);
  1365.          subi1(DIG(a,0), i, DIG(x,0), alen);
  1366.          }
  1367.       else {
  1368.          x = alcbignum(alen + 1);
  1369.          *DIG(x,0) = addi1(DIG(a,0), i, DIG(x,1), alen);
  1370.          }
  1371.       x->sign = a->sign;
  1372.       return mkdesc(x, dx);
  1373.       }
  1374. }
  1375.  
  1376. /*
  1377.  *  da - i -> dx
  1378.  */
  1379.  
  1380. static int bigsubi(da, i, dx)
  1381. dptr da, dx;
  1382. word i;
  1383. {
  1384.    struct b_bignum *a, *x; 
  1385.    word alen;
  1386.  
  1387.    if (i < 0)
  1388.       return bigaddi(da, -i, dx);
  1389.    else if (i != (DIGIT)i) {
  1390.       struct descrip td;
  1391.       char tdigits[INTBIGBLK];
  1392.  
  1393.       itobig(i, (struct b_bignum *)tdigits, &td);
  1394.       return bigsub(da, &td, dx);
  1395.       }
  1396.    else {
  1397.       alen = LEN(BigNum(da));
  1398.       if (blkreq(BigNeed(alen + 1)) == Error)
  1399.      return Error;
  1400.       a = BigNum(da);
  1401.       if (a->sign) {
  1402.          x = alcbignum(alen + 1);
  1403.          *DIG(x,0) = addi1(DIG(a,0), i, DIG(x,1), alen);
  1404.          }
  1405.       else {
  1406.          x = alcbignum(alen);
  1407.          subi1(DIG(a,0), i, DIG(x,0), alen);
  1408.          }
  1409.       x->sign = a->sign;
  1410.       return mkdesc(x, dx);
  1411.       }
  1412. }
  1413.  
  1414. /*
  1415.  *  da * i -> dx
  1416.  */
  1417.  
  1418. static int bigmuli(da, i, dx)
  1419. dptr da, dx;
  1420. word i;
  1421. {
  1422.    struct b_bignum *a, *x; 
  1423.    word alen;
  1424.  
  1425.    if (i <= -B || i >= B) {
  1426.       struct descrip td;
  1427.       char tdigits[INTBIGBLK];
  1428.  
  1429.       itobig(i, (struct b_bignum *)tdigits, &td);
  1430.       return bigmul(da, &td, dx);
  1431.       }
  1432.    else {
  1433.       alen = LEN(BigNum(da));
  1434.       if (blkreq(BigNeed(alen + 1)) == Error)
  1435.      return Error;
  1436.       a = BigNum(da);
  1437.       x = alcbignum(alen + 1);
  1438.       if (i >= 0)
  1439.          x->sign = a->sign;
  1440.       else {
  1441.          x->sign = 1 ^ a->sign;
  1442.          i = -i;
  1443.          }
  1444.       *DIG(x,0) = muli1(DIG(a,0), i, 0, DIG(x,1), alen);
  1445.       return mkdesc(x, dx);
  1446.       }
  1447. }
  1448.  
  1449. /*
  1450.  *  da / i -> dx
  1451.  */
  1452.  
  1453. static int bigdivi(da, i, dx)
  1454. dptr da, dx;
  1455. word i;
  1456. {
  1457.    struct b_bignum *a, *x; 
  1458.    word alen;
  1459.  
  1460.    if (i <= -B || i >= B) {
  1461.       struct descrip td;
  1462.       char tdigits[INTBIGBLK];
  1463.  
  1464.       itobig(i, (struct b_bignum *)tdigits, &td);
  1465.       return bigdiv(da, &td, dx);
  1466.       }
  1467.    else {
  1468.       alen = LEN(BigNum(da));
  1469.       if (blkreq(BigNeed(alen)) == Error)
  1470.      return Error;
  1471.       a = BigNum(da);
  1472.       x = alcbignum(alen);
  1473.       if (i >= 0)
  1474.          x->sign = a->sign;
  1475.       else {
  1476.          x->sign = 1 ^ a->sign;
  1477.          i = -i;
  1478.          }
  1479.       divi1(DIG(a,0), i, DIG(x,0), alen);
  1480.       return mkdesc(x, dx);
  1481.       }
  1482. }
  1483.  
  1484. /*
  1485.  *  da % i -> dx
  1486.  */
  1487.  
  1488. static int bigmodi(da, i, dx)
  1489. dptr da, dx;
  1490. word i;
  1491. {
  1492.    struct b_bignum *a, *temp;
  1493.    word alen;
  1494.    word x;
  1495.  
  1496.    if (i <= -B || i >= B) {
  1497.       struct descrip td;
  1498.       char tdigits[INTBIGBLK];
  1499.  
  1500.       itobig(i, (struct b_bignum *)tdigits, &td);
  1501.       return bigmod(da, &td, dx);
  1502.       }
  1503.    else {
  1504.       alen = LEN(BigNum(da));
  1505.       if (blkreq(BigNeed(alen)) == Error)
  1506.      return Error;
  1507.       a = BigNum(da);
  1508.       temp = alcbignum(alen);
  1509.       x = divi1(DIG(a,0), Abs(i), DIG(temp,0), alen);
  1510.       if (a->sign)
  1511.      x = -x;
  1512.       MakeInt(x, dx);
  1513.       return Success;
  1514.       }
  1515. }
  1516.  
  1517. /*
  1518.  *  da ^ i -> dx
  1519.  */
  1520.  
  1521. static int bigpowi(da, i, dx)
  1522. dptr da, dx;
  1523. word i;
  1524. {
  1525.    int n = WordBits;
  1526.  
  1527.    if (i > 0) {
  1528.       /* scan bits left to right.  skip leading 1. */
  1529.       while (--n >= 0)
  1530.          if (i & ((word)1 << n))
  1531.         break;
  1532.       /* then, for each zero, square the partial result;
  1533.          for each one, square it and multiply it by a */
  1534.       *dx = *da;
  1535.       while (--n >= 0) {
  1536.          if (bigmul(dx, dx, dx) == Error)
  1537.         return Error;
  1538.          if (i & ((word)1 << n))
  1539.             if (bigmul(dx, da, dx) == Error)
  1540.            return Error;
  1541.          }
  1542.       }
  1543.    else {
  1544.       MakeInt(0, dx);
  1545.       }
  1546.    return Success;
  1547. }
  1548.  
  1549. /*
  1550.  *  a ^ i -> dx
  1551.  */
  1552.  
  1553. static int bigpowii(a, i, dx)
  1554. word a, i;
  1555. dptr dx;
  1556. {
  1557.    word x, y;
  1558.    int n = WordBits;
  1559.    int isbig = 0;
  1560.  
  1561.    if (a == 0 || i <= 0) {              /* special cases */
  1562.       if (a == 0 && i <= 0)             /* 0 ^ negative -> error */
  1563.          RetError(-204, nulldesc);
  1564.       if (a == -1) {                    /* -1 ^ [odd,even] -> [-1,+1] */
  1565.          if (!(i & 1))
  1566.         a = 1;
  1567.          }
  1568.       else if (a != 1) {                /* 1 ^ any -> 1 */
  1569.          a = 0;
  1570.          }                   /* others ^ negative -> 0 */
  1571.       MakeInt(a, dx);
  1572.       }
  1573.    else {
  1574.       struct descrip td;
  1575.       char tdigits[INTBIGBLK];
  1576.  
  1577.       /* scan bits left to right.  skip leading 1. */
  1578.       while (--n >= 0)
  1579.          if (i & ((word)1 << n))
  1580.         break;
  1581.       /* then, for each zero, square the partial result;
  1582.          for each one, square it and multiply it by a */
  1583.       x = a;
  1584.       while (--n >= 0) {
  1585.          if (isbig) {
  1586.             if (bigmul(dx, dx, dx) == Error)
  1587.            return Error;
  1588.         }
  1589.          else {
  1590.             y = mul(x, x);
  1591.             if (!over_flow)
  1592.                x = y;
  1593.             else {
  1594.                itobig(x, (struct b_bignum *)tdigits, &td);
  1595.                if (bigmul(&td, &td, dx) == Error)
  1596.                  return Error;
  1597.                isbig = (Type(*dx) == T_Bignum);
  1598.                } 
  1599.             }
  1600.          if (i & ((word)1 << n)) {
  1601.             if (isbig) {
  1602.                if (bigmuli(dx, a, dx) == Error)
  1603.           return Error;
  1604.            }
  1605.             else {
  1606.                y = mul(x, a);
  1607.                if (!over_flow)
  1608.                   x = y;
  1609.                else {
  1610.                   itobig(x, (struct b_bignum *)tdigits, &td);
  1611.                   if (bigmuli(&td, a, dx) == Error)
  1612.              return Error;
  1613.                   isbig = (Type(*dx) == T_Bignum);
  1614.                   }
  1615.                }
  1616.             }
  1617.          }
  1618.       if (!isbig) {
  1619.      MakeInt(x, dx);
  1620.      }
  1621.       }
  1622.    return Success;
  1623. }
  1624.  
  1625. /*
  1626.  *  negative if da < i
  1627.  *  zero if da == i
  1628.  *  positive if da > i
  1629.  */  
  1630.   
  1631. static word bigcmpi(da, i)
  1632. dptr da;
  1633. word i;
  1634. {
  1635.    struct b_bignum *a = BigNum(da);
  1636.    word alen = LEN(a);
  1637.  
  1638.    if (i > -B && i < B) {
  1639.       if (i >= 0)
  1640.          if (a->sign)
  1641.         return -1;
  1642.          else
  1643.         return cmpi1(DIG(a,0), i, alen);
  1644.       else
  1645.          if (a->sign)
  1646.         return -cmpi1(DIG(a,0), -i, alen);
  1647.          else
  1648.         return 1;
  1649.       }
  1650.    else {
  1651.       struct descrip td;
  1652.       char tdigits[INTBIGBLK];
  1653.  
  1654.       itobig(i, (struct b_bignum *)tdigits, &td);
  1655.       return bigcmp(da, &td);
  1656.       }
  1657. }
  1658.  
  1659.  
  1660. /* These are all straight out of Knuth vol. 2, Sec. 4.3.1. */
  1661.  
  1662. /*
  1663.  *  (u,n) + (v,n) -> (w,n)
  1664.  *
  1665.  *  returns carry, 0 or 1
  1666.  */
  1667.  
  1668. static DIGIT add1(u, v, w, n)
  1669. DIGIT *u, *v, *w;
  1670. word n;
  1671. {
  1672.    uword dig, carry; 
  1673.    word i;
  1674.  
  1675.    carry = 0;
  1676.    for (i = n; --i >= 0; ) {
  1677.       dig = (uword)u[i] + v[i] + carry;
  1678.       w[i] = lo(dig);
  1679.       carry = hi(dig);
  1680.       }
  1681.    return carry;
  1682. }
  1683.  
  1684. /*
  1685.  *  (u,n) - (v,n) -> (w,n)
  1686.  *
  1687.  *  returns carry, 0 or -1
  1688.  */
  1689.  
  1690. static word sub1(u, v, w, n)
  1691. DIGIT *u, *v, *w;
  1692. word n;
  1693. {
  1694.    uword dig, carry; 
  1695.    word i;
  1696.  
  1697.    carry = 0;
  1698.    for (i = n; --i >= 0; ) {
  1699.       dig = (uword)u[i] - v[i] + carry;
  1700.       w[i] = lo(dig);
  1701.       carry = signed_hi(dig);
  1702.       }
  1703.    return carry;
  1704. }
  1705.  
  1706. /*
  1707.  *  (u,n) * (v,m) -> (w,m+n)
  1708.  */
  1709.  
  1710. static novalue mul1(u, v, w, n, m)
  1711. DIGIT *u, *v, *w;
  1712. word n, m;
  1713. {
  1714.    word i, j;
  1715.    uword dig, carry;
  1716.  
  1717.    bdzero(&w[m], n);
  1718.  
  1719.    for (j = m; --j >= 0; ) {
  1720.       carry = 0;
  1721.       for (i = n; --i >= 0; ) {
  1722.          dig = (uword)u[i] * v[j] + w[i+j+1] + carry;
  1723.          w[i+j+1] = lo(dig);
  1724.          carry = hi(dig);
  1725.          }
  1726.       w[j] = carry;
  1727.       }
  1728. }
  1729.  
  1730. /*
  1731.  *  (a,m+n) / (b,n) -> (q,m+1) (r,n)
  1732.  *
  1733.  *  if q or r is NULL, the quotient or remainder is discarded
  1734.  */
  1735.  
  1736. static novalue div1(a, b, q, r, m, n)
  1737. DIGIT *a, *b, *q, *r;
  1738. word m, n;
  1739. {
  1740.    uword qhat, rhat;
  1741.    uword dig, carry;
  1742.    struct b_bignum *tu, *tv;
  1743.    DIGIT *u, *v;
  1744.    word d;
  1745.    word i, j;
  1746.  
  1747.    /* blkreq's done in calling routines */
  1748.  
  1749.    tu = alcbignum(m + n + 1);
  1750.    tv = alcbignum(n);
  1751.    u = DIG(tu,0);
  1752.    v = DIG(tv,0);
  1753.  
  1754.    /* D1 */
  1755.    for (d = 0; d < NB; d++)
  1756.       if (b[0] & (1 << (NB - 1 - d)))
  1757.          break;
  1758.  
  1759.    u[0] = shifti1(a, d, (DIGIT)0, &u[1], m+n);
  1760.    shifti1(b, d, (DIGIT)0, v, n);
  1761.  
  1762.    /* D2, D7 */
  1763.    for (j = 0; j <= m; j++) {
  1764.       /* D3 */
  1765.       if (u[j] == v[0]) {
  1766.          qhat = B - 1;
  1767.          rhat = (uword)v[0] + u[j+1];
  1768.          }
  1769.       else {
  1770.          uword numerator = dbl(u[j], u[j+1]);
  1771.          qhat = numerator / (uword)v[0];
  1772.          rhat = numerator % (uword)v[0];
  1773.          }
  1774.  
  1775.       while (rhat < B && qhat * v[1] > dbl(rhat, u[j+2])) {
  1776.          qhat -= 1;
  1777.          rhat += v[0];
  1778.          }
  1779.             
  1780.       /* D4 */
  1781.       carry = 0;
  1782.       for (i = n; i > 0; i--) {
  1783.          dig = u[i+j] - v[i-1] * qhat + carry;       /* -BSQ+B .. B-1 */
  1784.          u[i+j] = lo(dig);
  1785.          if ((uword)dig < B)
  1786.             carry = hi(dig);
  1787.          else carry = hi(dig) | -B;
  1788.          }
  1789.       carry = (word)(carry + u[j]) < 0;
  1790.  
  1791.       /* D5 */
  1792.       if (q)
  1793.      q[j] = qhat;
  1794.  
  1795.       /* D6 */
  1796.       if (carry) {
  1797.          if (q)
  1798.         q[j] -= 1;
  1799.          carry = 0;
  1800.          for (i = n; i > 0; i--) {
  1801.             dig = (uword)u[i+j] + v[i-1] + carry;
  1802.             u[i+j] = lo(dig);
  1803.             carry = hi(dig);
  1804.             }
  1805.          }
  1806.       }
  1807.  
  1808.    if (r) {
  1809.       if (d == 0)
  1810.          shifti1(&u[m+1], (word)d, (DIGIT)0, r, n);
  1811.       else
  1812.          r[0] = shifti1(&u[m+1], (word)(NB - d), u[m+n]>>d, &r[1], n - 1);
  1813.       }
  1814. }
  1815.  
  1816. /*
  1817.  *  - (u,n) -> (w,n)
  1818.  *
  1819.  */
  1820.  
  1821. static novalue compl1(u, w, n)
  1822. DIGIT *u, *w;
  1823. word n;
  1824. {
  1825.    uword dig, carry = 0;
  1826.    word i;
  1827.  
  1828.    for (i = n; --i >= 0; ) {
  1829.       dig = carry - u[i];
  1830.       w[i] = lo(dig);
  1831.       carry = signed_hi(dig);
  1832.       }
  1833. }
  1834.  
  1835. /*
  1836.  *  (u,n) : (v,n)
  1837.  */
  1838.  
  1839. static word cmp1(u, v, n)
  1840. DIGIT *u, *v;
  1841. word n;
  1842. {
  1843.    word i;
  1844.  
  1845.    for (i = 0; i < n; i++)
  1846.       if (u[i] != v[i])
  1847.          return u[i] > v[i] ? 1 : -1;
  1848.    return 0;
  1849. }
  1850.  
  1851. /*
  1852.  *  (u,n) + k -> (w,n)
  1853.  *
  1854.  *  k in 0 .. B-1
  1855.  *  returns carry, 0 or 1
  1856.  */
  1857.  
  1858. static DIGIT addi1(u, k, w, n)
  1859. DIGIT *u, *w;
  1860. word k;
  1861. word n;
  1862. {
  1863.    uword dig, carry;
  1864.    word i;
  1865.     
  1866.    carry = k;
  1867.    for (i = n; --i >= 0; ) {
  1868.       dig = (uword)u[i] + carry;
  1869.       w[i] = lo(dig);
  1870.       carry = hi(dig);
  1871.       }
  1872.    return carry;
  1873. }
  1874.  
  1875. /*
  1876.  *  (u,n) - k -> (w,n)
  1877.  *
  1878.  *  k in 0 .. B-1
  1879.  *  u must be greater than k
  1880.  */
  1881.  
  1882. static novalue subi1(u, k, w, n)
  1883. DIGIT *u, *w;
  1884. word k;
  1885. word n;
  1886. {
  1887.    uword dig, carry;
  1888.    word i;
  1889.     
  1890.    carry = -k;
  1891.    for (i = n; --i >= 0; ) {
  1892.       dig = (uword)u[i] + carry;
  1893.       w[i] = lo(dig);
  1894.       carry = signed_hi(dig);
  1895.       }
  1896. }
  1897.  
  1898. /*
  1899.  *  (u,n) * k + c -> (w,n)
  1900.  *
  1901.  *  k in 0 .. B-1
  1902.  *  returns carry, 0 .. B-1
  1903.  */
  1904.  
  1905. static DIGIT muli1(u, k, c, w, n)
  1906. DIGIT *u, *w;
  1907. word k;
  1908. int c;
  1909. word n;
  1910. {
  1911.    uword dig, carry;
  1912.    word i;
  1913.  
  1914.    carry = c;
  1915.    for (i = n; --i >= 0; ) {
  1916.       dig = (uword)k * u[i] + carry;
  1917.       w[i] = lo(dig);
  1918.       carry = hi(dig);
  1919.       }
  1920.    return carry;
  1921. }
  1922.  
  1923. /*
  1924.  *  (u,n) / k -> (w,n)
  1925.  *
  1926.  *  k in 0 .. B-1
  1927.  *  returns remainder, 0 .. B-1
  1928.  */
  1929.  
  1930. static DIGIT divi1(u, k, w, n)
  1931. DIGIT *u, *w;
  1932. word k;
  1933. word n;
  1934. {
  1935.    uword dig, remain;
  1936.    word i;
  1937.  
  1938.    remain = 0;
  1939.    for (i = 0; i < n; i++) {
  1940.       dig = dbl(remain, u[i]);
  1941.       w[i] = dig / k;
  1942.       remain = dig % k;
  1943.       }
  1944.    return remain;
  1945. }
  1946.  
  1947. /*
  1948.  *  ((u,n) << k) + c -> (w,n)
  1949.  *
  1950.  *  k in 0 .. NB-1
  1951.  *  c in 0 .. B-1 
  1952.  *  returns carry, 0 .. B-1
  1953.  */
  1954.  
  1955. static DIGIT shifti1(u, k, c, w, n)
  1956. DIGIT *u, c, *w;
  1957. word k;
  1958. word n;
  1959. {
  1960.    uword dig;
  1961.    word i;
  1962.  
  1963.    if (k == 0) {
  1964.       bdcopy(u, w, n);
  1965.       return 0;
  1966.       }
  1967.     
  1968.    for (i = n; --i >= 0; ) {
  1969.       dig = ((uword)u[i] << k) + c;
  1970.       w[i] = lo(dig);
  1971.       c = hi(dig);
  1972.       }
  1973.    return c;
  1974. }
  1975.  
  1976. /*
  1977.  *  (u,n) : k
  1978.  *
  1979.  *  k in 0 .. B-1
  1980.  */
  1981.  
  1982. static word cmpi1(u, k, n)
  1983. DIGIT *u;
  1984. word k;
  1985. word n;
  1986. {
  1987.    word i;
  1988.  
  1989.    for (i = 0; i < n-1; i++)
  1990.       if (u[i])
  1991.      return 1;
  1992.    if (u[n - 1] == (DIGIT)k)
  1993.       return 0;
  1994.    return u[n - 1] > (DIGIT)k ? 1 : -1;
  1995. }
  1996.  
  1997. static novalue bdzero(dest, l)
  1998. DIGIT *dest;
  1999. word l;
  2000. {
  2001.    word i;
  2002.  
  2003.    for (i = 0; i < l; i++)
  2004.       dest[i] = 0;
  2005. }
  2006.  
  2007. static novalue bdcopy(src, dest, l)
  2008. DIGIT *src, *dest;
  2009. word l;
  2010. {
  2011.    word i;
  2012.  
  2013.    for (i = 0; i < l; i++)
  2014.       dest[i] = src[i];
  2015. }
  2016. #else                    /* LargeInts */
  2017. static char x;            /* prevent empty module */
  2018. #endif                    /* LargeInts */
  2019.